/*
 * @lc app=leetcode.cn id=1738 lang=typescript
 *
 * [1738] 找出第 K 大的异或坐标值
 */

// @lc code=start

type QuickSort = (a: number[], l: number, r: number) => void;
type Medina = (l: number, m: number, r: number) => number;

function kthLargestValue(matrix: number[][], k: number): number {
  const m = matrix.length;
  const n = matrix[0].length;
  // 二维前缀和数组
  const preSum = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  // 快速排序
  const quicksort: QuickSort = (arr, l, r) => {
    if (l >= r) return;
    let x = l;
    let y = r;
    let base = medina(arr[l], arr[(l + r) >> 1], arr[r]);
    while (x < y) {
      while (x < y && arr[y] >= base) {
        y--;
      }
      if (x < y) {
        arr[x++] = arr[y];
      }
      while (x < y && arr[x] <= base) {
        x++;
      }
      if (x < y) {
        arr[y--] = arr[x];
      }
    }
    arr[x] = base;
    quicksort(arr, l, x - 1);
    quicksort(arr, x + 1, r);
  };
  // 三点取中法
  const medina: Medina = (a, b, c) => {
    if (a > b) [a, b] = [b, a];
    if (a > c) [a, c] = [c, a];
    if (b > c) [b, c] = [c, b];
    return b;
  };

  const result: number[] = [];
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      preSum[i][j] =
        preSum[i - 1][j] ^ preSum[i][j - 1] ^ preSum[i - 1][j - 1] ^ matrix[i - 1][j - 1];
      result.push(preSum[i][j]);
    }
  }
  // 快速排序
  quicksort(result, 0, result.length - 1);
  return result[result.length - k];
}
// @lc code=end
